#include <boost/numeric/ublas/triangular.hpp>
#include <boost/numeric/ublas/io.hpp>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
namespace bst = boost::numeric::ublas;

int as_dp(const std::vector<int>& s, const std::vector<int>& f, bst::triangular_matrix<int,bst::upper> & c, bst::triangular_matrix<int,bst::upper>& r) {
	c.resize(s.size()+1,s.size()+1);
	r.resize(s.size()+1,s.size()+1);
	for (int i = 0; i <=s.size(); ++i) 
		c(i,i) = 0;
	for (int i = 0; i <= s.size() - 1; ++i) {
		if (i == s.size()-1) { //s.size() == 1;
			c(i,i+1) = 1;
			break;
		}
		if (i == 0) {
			if (f[i] <= s[i+1])
				c(i,i+1) = 1;
			else
				c(i,i+1) = 0; //overlapped
		}
		else if (i == s.size()-1) {
			if (f[i-1] <= s[i])
				c(i,i+1) = 1;
			else
				c(i,i+1) = 0; //overlapped
		}
		else { //at least three elements
			if (f[i-1] <= s[i] && f[i] <= s[i+1])
				c(i,i+1) = 1;
			else 
				c(i,i+1) = 0; //overlapped
		}
	}
	for (int i = s.size()-2; i >= 0; --i) {
		for (int j = i+2; j <= s.size(); ++j) {
			c(i,j) = 0;
			r(i,j) = -1; // no valid a[k] found yet
			int lower, upper;
			if ( i == 0 )
				lower = std::numeric_limits<int>::min();
			else
				lower = f[i-1];
			if ( j == s.size() )
				upper = std::numeric_limits<int>::max();
			else
				upper = s[j];
			for (int k = i; k <= j-1; ++k) {
				if(s[k] >= lower && f[k] <= upper) { //valid a[k]
					int tmp = c(i,k) + c(k+1,j) + 1;
					if (tmp > c(i,j)){
						c(i,j) = tmp;
						r(i,j) = k;
					}
				}
			}
		}
	}
	return c(0,s.size());
}

//call as_dp_print(r, 0, s.size())
void as_dp_print(const bst::triangular_matrix<int,bst::upper>& r, int i, int j) {
	if ( i < j) {
		int k = r(i,j);
		if ( k < 0 )
			return;
		std::cout << "a[" << k << "] ";
		as_dp_print(r, i, k);
		as_dp_print(r, k+1, j);
	}
}

void test_as_dp() {
	int sa[] = {1,3,0,5,3,5,6,8,8,2,12};
	int fa[] = {4,5,6,7,9,9,10,11,12,14,16};
	std::vector<int> s(sa, sa+sizeof(sa)/sizeof(int));
	std::vector<int> f(fa, fa+sizeof(sa)/sizeof(int));
	bst::triangular_matrix<int,bst::upper> c,r;
	std::cout << "the maximum size is " << as_dp(s,f,c,r) << std::endl;
	as_dp_print(r,0,s.size()); std::cout << std::endl;
}

struct Activity {
	int start, finish;
};
template <bool byfinish>
struct ActivityComp {
	bool operator()(const Activity & a, const Activity & b) { 
		return byfinish ? (a.finish < b.finish) : (a.start < b.start);
	}
};

void as_greedy_recursive(const std::vector<Activity> & a, int k) {
	int m = k + 1;
	while (m < a.size() && k >= 0 && a[m].start < a[k].finish)
		++m;
	if (m < a.size() ) {
		std::cout << "a[" << m << "](" << a[m].start << ',' << a[m].finish << ") ";
		as_greedy_recursive(a,m);
	}
}

//call (a,a.size());
void as_greedy_recursive_last_start(const std::vector<Activity> & a, int k) {
	int m = k - 1;
	while (m >= 0 && k < a.size() && a[m].finish > a[k].start)
		--m;
	if (m >= 0 ) {
		std::cout << "a[" << m << "](" << a[m].start << ',' << a[m].finish << ") ";
		as_greedy_recursive_last_start(a,m);
	}
}

void as_greedy_iterative(std::vector<Activity> & a)  {
	ActivityComp<true> sortbyfinish;
	std::stable_sort(a.begin(), a.end(), sortbyfinish);
	for (int i = 0, last = std::numeric_limits<int>::min(); i < a.size(); ++i) {
		if (a[i].start > last) {
			std::cout << "a[" << i << "](" << a[i].start << ',' << a[i].finish << ") ";
			last = a[i].finish;
		}
	}
	std::cout << std::endl;
}

void as_greedy_iterative_last_start(std::vector<Activity> & a) {
	ActivityComp<false> sortbystart;
	std::stable_sort(a.begin(), a.end(), sortbystart);
	for (int i = a.size()-1, last = std::numeric_limits<int>::max(); i >= 0; --i) {
		if (a[i].finish < last) {
			std::cout << "a[" << i << "](" << a[i].start << ',' << a[i].finish << ") ";
			last = a[i].start;
		}
	}
	std::cout << std::endl;
}

void test_as_greedy(){
	int sa[] = {1,3,0,5,3,5,6,8,8,2,12};
	int fa[] = {4,5,6,7,9,9,10,11,12,14,16};
	std::vector<Activity> a(sizeof(sa)/sizeof(int));
	for (int i = 0; i < a.size(); ++i) {
		a[i].start = sa[i];
		a[i].finish = fa[i];
	}
	std::cout << "iterative\n";
	as_greedy_iterative(a);
	std::cout << "recursive\n";
	as_greedy_recursive(a,-1); std::cout << std::endl;
	std::cout << "iterative by last start\n";
	as_greedy_iterative_last_start(a); 
	std::cout << "recursive by last start\n";
	as_greedy_recursive_last_start(a,a.size()); std::cout << std::endl;
}

void test_as(){
	std::cout << "***** Dynamic Programming method *****\n";
	test_as_dp();
	std::cout << "***** Greedy method *****\n";
	test_as_greedy();
}